home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 5_11.lha / 5_11 / tst.c < prev    next >
Text File  |  1993-08-08  |  5KB  |  307 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. include <stream.h>
  6. include <string.h>
  7. include <ctype.h>
  8.  
  9. include <error.h>
  10.  
  11. include "5_10a.h"    // class table
  12. include "5_10a1.c"    // table::lock
  13. include "5_10a2.c"    // table::table()
  14. include "5_10a3.c"    // table::~table()
  15.  
  16. include "5_11A.h"    // enum exprtype
  17. include "5_11B.h"    // struct tree
  18. include "5_11C.h"    // struct token
  19. include "5_11D.h"    // class expr
  20.  
  21. tatic token curr_tok;
  22.  
  23. include "5_11h.c"    // forward declarations
  24.  
  25. tatic tree* term(istream& input, table *variables)
  26.  
  27.    tree* left = prim(input, variables);
  28.  
  29.    for (;;)
  30. switch (curr_tok.type)
  31.     {
  32.     case MUL:
  33.     case DIV:
  34.     tree* head = new tree;
  35.     head->type = curr_tok.type;
  36.     head->left = left;
  37.     get_token(input, variables);    // eat '*','/'
  38.     head->right = prim(input, variables);
  39.     left = head;
  40.     break;
  41.  
  42.     default:        // collapse node
  43.     return left;
  44.     }
  45.  
  46.  
  47.  
  48. ree *expandtree(istream &input, table *variables)
  49.  
  50.    if (curr_tok.type == END)
  51. {
  52. tree *ret = new tree;
  53. ret->type = NUMBER;
  54. ret->value = 0;
  55. return ret;
  56. }
  57.  
  58. include "5_11c.c"    // else get series of expressions
  59.  
  60.  
  61. tatic tree* prim(istream& input, table *variables)
  62.  
  63.    tree* ret = new tree;
  64.  
  65.    switch (curr_tok.type)
  66. {
  67. case NUMBER:
  68.     ret->type = NUMBER;
  69.     ret->value = curr_tok.value;
  70.     get_token(input, variables);        // skip number
  71.     return ret;
  72.  
  73. case MINUS:
  74.     ret->type = MINUS;
  75.     get_token(input, variables);        // skip '-'
  76.     ret->left = prim(input, variables);
  77.     ret->right = 0;
  78.     return ret;
  79.  
  80. case LP:
  81.     ret->type = LP;
  82.     get_token(input, variables);        // skip '('
  83.     ret->left = get_expr(input, variables);
  84.     if (curr_tok.type != RP)
  85.         {
  86.     error(") expected");
  87.     break;
  88.     }
  89.     get_token(input, variables);        // skip ')'
  90.     return ret;
  91.  
  92. case END:
  93.     error("end of expression unexpected");
  94.     break;
  95.  
  96. include "5_11b.c"    // case NAME
  97.  
  98. default:
  99.     error("prim: unknown type within tree, %c", curr_tok.type);
  100.     break;
  101. }
  102.  
  103.    // error case
  104.    ret->value = 0;
  105.    ret->type = NUMBER;
  106.    return ret;
  107.  
  108.  
  109.  
  110. xpr:: expr(char* s)
  111.  
  112.    istream input(strlen(s), s);
  113.    evaluated = 0;
  114.    get_token(input, &variables);
  115.    head = expandtree(input, &variables);
  116.  
  117.  
  118. tatic tree* get_expr(istream& input, table *variables)
  119.  
  120.    tree* left = term(input, variables);
  121.  
  122.    for (;;)
  123. switch (curr_tok.type)
  124.     {
  125.     case PLUS:
  126.     case MINUS:
  127.     tree* head = new tree;
  128.     head->type = curr_tok.type;
  129.     head->left = left;
  130.     get_token(input, variables);    // eat '+','-'
  131.     head->right = term(input, variables);
  132.     left = head;
  133.     break;
  134.  
  135.     default:        // collapse node
  136.     return left;
  137.     }
  138.  
  139.  
  140. / Evaluate the given expression tree
  141. nt treeval(tree* head, table *variables)
  142.  
  143.    if (head)
  144. switch (head->type)
  145.     {
  146.     case PLUS:
  147.     return treeval(head->left, variables) +
  148.            treeval(head->right, variables);
  149.  
  150.     case MINUS:
  151.     if (head->right)
  152.         return treeval(head->left, variables) -
  153.            treeval(head->right, variables);
  154.     else
  155.         return -treeval(head->left, variables);
  156.  
  157.     case DIV:
  158.         int l = treeval(head->left, variables);
  159.         int r = treeval(head->right, variables);
  160.     if (r != 0)
  161.         return l / r;
  162.     else
  163.         return error("division by 0");
  164.  
  165.     case MUL:
  166.     return treeval(head->left, variables) *
  167.            treeval(head->right, variables);
  168.  
  169.     case NUMBER:
  170.     return head->value;
  171.  
  172.     case LP:
  173.     return treeval(head->left, variables);
  174.  
  175. include "5_11e.c"    // case ASSIGN, NAME
  176.  
  177.     case RP:
  178.     case END:
  179.     error ("invalid type within treeval, '%c'", head->type);
  180.     break;
  181.     }
  182.  
  183.    else
  184. error("NULL node found");
  185.    return 0;
  186.  
  187.  
  188. / print out the tree in infix format
  189. tatic void infixprint(tree* head)
  190.  
  191.    cout << "( ";
  192.    if (head)
  193. switch (head->type)
  194.     {
  195.     case PLUS:
  196.     case DIV:
  197.     case MUL:
  198.     infixprint (head->left);
  199.     cout << chr (head->type) << " ";
  200.     infixprint (head->right);
  201.     break;
  202.  
  203.     case MINUS:
  204.     if (head->right)
  205.         {
  206.         infixprint (head->left);
  207.         cout << "- ";
  208.         infixprint (head->right);
  209.         }
  210.  
  211.     else
  212.         {
  213.         cout << "- ";
  214.         infixprint (head->left);
  215.         }
  216.     break;
  217.  
  218.     case NUMBER:
  219.     cout << head->value;
  220.     break;
  221.  
  222.     case LP:
  223.     infixprint (head->left);
  224.     break;
  225.  
  226. include "5_11i.c"
  227.  
  228.     case RP:
  229.     case SEMICOLON:
  230.     case END:
  231.     error ("invalid type within infixprint, '%c'", head->type);
  232.     break;
  233.     }
  234.  
  235.    else
  236. error ("NULL node found");
  237.  
  238.    cout << " ) ";
  239.  
  240.  
  241. include "5_11d.c"    // expr::eval()
  242.  
  243. tatic void get_token(istream &input, table *variables)
  244.  
  245.    char ch;
  246.    do  {    // skip whitespace
  247. if (!input.get(ch))
  248.     { curr_tok.type = END; return; }
  249.    } while (isspace(ch));
  250.  
  251.    switch (ch)
  252. {
  253. include "5_11g.c"
  254.     curr_tok.type = ch;
  255.     return;
  256.  
  257. case '0': case '1': case '2': case '3':
  258. case '4': case '5': case '6': case '7':
  259. case '8': case '9':
  260.     input.putback(ch);
  261.     input >> curr_tok.value;
  262.     curr_tok.type = NUMBER;
  263.     return;
  264.  
  265. include "5_11a.c"    // isalpha()
  266.     error("bad token, ch='%c'", ch);
  267.     curr_tok.type = END;
  268.     return;
  269. }
  270.  
  271.  
  272. include "5_11f.c"    // expr::print()
  273.  
  274. har *strs[] =
  275.  
  276.    "",
  277.    "1 ",
  278.    "2*3 ",
  279.    "2-3 ",
  280.    "5/2",
  281.    "123/4+123*4-3",
  282.    "a=5/2; 57+a-3 ",
  283.    0
  284. ;
  285.  
  286. oid lookat(char *s)
  287.  
  288.    cout << "x = '" << s << "'\n";
  289.    expr x(s);
  290.    cout << "x = "; x.print(); cout << "\n";
  291.    cout << "x = " << x.eval() << "\n";
  292.    cout << "\n";
  293.  
  294.  
  295. ain(int argc, char **argv)
  296.  
  297.    if (argc > 1)
  298. while (*++argv)
  299.     lookat(*argv);
  300.  
  301.    else
  302. for (int i = 0; strs[i]; i++)
  303.     lookat(strs[i]);
  304.  
  305.    return 0;
  306.  
  307.